{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Size Subarray Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSubArrayLen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度最小的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个含有&nbsp;<code>n</code><strong>&nbsp;</strong>个正整数的数组和一个正整数 <code>target</code><strong> 。</strong></p>\n",
    "\n",
    "<p>找出该数组中满足其总和大于等于<strong> </strong><code>target</code><strong> </strong>的长度最小的 <strong>连续子数组</strong>&nbsp;<code>[nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>]</code> ，并返回其长度<strong>。</strong>如果不存在符合条件的子数组，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 7, nums = [2,3,1,2,4,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>子数组&nbsp;<code>[4,3]</code>&nbsp;是该条件下的长度最小的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 4, nums = [1,4,4]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 11, nums = [1,1,1,1,1,1,1,1]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果你已经实现<em> </em><code>O(n)</code> 时间复杂度的解法, 请尝试设计一个 <code>O(n log(n))</code> 时间复杂度的解法。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-size-subarray-sum](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-size-subarray-sum](https://leetcode.cn/problems/minimum-size-subarray-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[2,3,1,2,4,3]', '4\\n[1,4,4]', '11\\n[1,1,1,1,1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        minLength = sys.maxsize\n",
    "        p1, p2 = 0, 0\n",
    "        currSum = 0\n",
    "        while p2 < len(nums):\n",
    "            currSum += nums[p2]\n",
    "            if currSum >= target:\n",
    "                while p1 <= p2 and currSum - nums[p1] >= target:\n",
    "                    currSum -= nums[p1]\n",
    "                    p1 += 1\n",
    "                minLength = min(minLength, p2-p1+1)\n",
    "            p2 += 1\n",
    "        return 0 if minLength == sys.maxsize else minLength\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "        \"\"\"\n",
    "        :type s: int\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        start = 0\n",
    "        end = -1\n",
    "        min_size = n + 1\n",
    "        sum = 0\n",
    "        while end < n - 1:\n",
    "            end += 1\n",
    "            sum += nums[end]\n",
    "            while sum - nums[start] >= s:\n",
    "                sum -= nums[start]\n",
    "                start += 1\n",
    "            if sum >= s:\n",
    "                min_size = min(min_size, end - start + 1)\n",
    "\n",
    "        if min_size == n + 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return min_size\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "        \"\"\"\n",
    "        :type s: int\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        l,r = 0,-1\n",
    "        n = len(nums)\n",
    "        res,total = n+1,0\n",
    "        while r+1 <n and l<n:\n",
    "            if total<s:\n",
    "                r+=1\n",
    "                total += nums[r]\n",
    "            if total>=s:\n",
    "                res = min(res,r-l+1)\n",
    "            while total>=s:\n",
    "                total -= nums[l]\n",
    "                l+=1\n",
    "                if total>=s:\n",
    "                    res = min(res,r-l+1)\n",
    "        if res==n+1:\n",
    "            return 0\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "      if len(nums)==0:\n",
    "        return 0\n",
    "      i,j,l= 0,0,float('inf')\n",
    "      su = 0\n",
    "      while j<len(nums):\n",
    "        su += nums[j] \n",
    "        j+=1\n",
    "        while su>=s:\n",
    "            l = min(l,j-i)\n",
    "            su -= nums[i]\n",
    "            i+=1\n",
    "        print(i,j)\n",
    "            \n",
    "      return l if l!=float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "        \"\"\"\n",
    "        :type s: int\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums: return 0\n",
    "        res = []\n",
    "        i,j=0,0\n",
    "        cursum = nums[0]\n",
    "        while True:\n",
    "            if cursum<s:\n",
    "                j += 1\n",
    "                if j>len(nums)-1:break\n",
    "                cursum += nums[j]\n",
    "            elif cursum>=s:\n",
    "                res.append(j-i+1)\n",
    "                cursum -= nums[i]\n",
    "                i += 1\n",
    "        if not res: return 0\n",
    "        else: return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minSubArrayLen(self, s, nums):\n",
    "\t\t\"\"\"\n",
    "\t\t:type s: int\n",
    "\t\t:type nums: List[int]\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\t\tp1 = 0\n",
    "\t\tsumArr = [0 for i in range(len(nums))]\n",
    "\t\tresult = (0, len(nums) * 2)\n",
    "\t\tfor i in range(len(nums)):\n",
    "\t\t\tsumArr[i] = nums[i] if i == 0 else nums[i] + sumArr[i-1]\n",
    "\t\t\tif sumArr[i] >= s:\n",
    "\t\t\t\twhile sumArr[i] - sumArr[p1] >= s:\n",
    "\t\t\t\t\tp1 = p1 + 1\n",
    "\t\t\t\tif (i - p1 + 1) < (result[1] - result[0] + 1):\n",
    "\t\t\t\t\tresult = (p1, i)\n",
    "\t\t\t\t\tprint(result)\n",
    "\t\t\t\t\n",
    "\t\treturn (result[1] - result[0] + 1) if (result[1] - result[0]) != len(nums)*2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "        \"\"\"\n",
    "        :type s: int\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        total=0\n",
    "        douyoushei=[]\n",
    "        jishu=[]\n",
    "        if sum(nums)<s:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            douyoushei.append(nums[i])\n",
    "            total+=nums[i]\n",
    "            if total>=s:\n",
    "                jishu.append(len(douyoushei))\n",
    "            while total-douyoushei[0]>=s:\n",
    "                total-=douyoushei[0]\n",
    "                jishu.append(len(douyoushei)-1)\n",
    "                del douyoushei[0]\n",
    "        return min(jishu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if max(nums) >= s:\n",
    "            return 1\n",
    "        dp = [[-1, 0] for i in range(len(nums))]\n",
    "        ss = 0\n",
    "        i = -1\n",
    "        while ss < s and i < len(nums) - 1:\n",
    "            i += 1\n",
    "            ss += nums[i]\n",
    "        if ss < s:\n",
    "            return 0\n",
    "        k = 0\n",
    "        while ss >= s:\n",
    "            ss -= nums[k]\n",
    "            k += 1\n",
    "        k -= 1\n",
    "        ss += nums[k]\n",
    "        dp[i] = [k, ss]\n",
    "        ans = i + 1 - k\n",
    "        for j in range(i + 1, len(nums)):\n",
    "            ss = dp[j - 1][1] + nums[j]\n",
    "            k = dp[j - 1][0]\n",
    "            while ss >= s:\n",
    "                ss -= nums[k]\n",
    "                k += 1\n",
    "            k -= 1\n",
    "            ss += nums[k]\n",
    "            dp[j] = [k, ss]\n",
    "            ans = min(j - k + 1, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums):\n",
    "        \"\"\"\n",
    "        :type s: int\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = 0\n",
    "        r = 0\n",
    "        sum_all = 0\n",
    "        nums_len = len(nums)\n",
    "        minLength = nums_len + 1\n",
    "        while l < nums_len:\n",
    "            if r < nums_len and sum_all < s:\n",
    "                sum_all += nums[r]\n",
    "                r += 1\n",
    "            else:\n",
    "                sum_all -= nums[l]\n",
    "                l += 1\n",
    "\n",
    "            if sum_all >= s:\n",
    "                minLength = min(minLength, r - l)\n",
    "\n",
    "        if minLength == nums_len + 1:\n",
    "            return 0\n",
    "\n",
    "        return minLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if sum(nums) < s:\n",
    "            return 0\n",
    "        temp = []\n",
    "        sums = 0\n",
    "        min_length = len(nums)\n",
    "        for num in nums:\n",
    "            temp.append(num)\n",
    "            sums += num\n",
    "            while sums >= s:\n",
    "                min_length = min(min_length, len(temp))\n",
    "                x = temp.pop(0)\n",
    "                sums -= x\n",
    "        return min_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = right = 0\n",
    "        ans = 1 << 31\n",
    "        tmps = 0\n",
    "        while right < n:\n",
    "            c = nums[right]\n",
    "            right += 1\n",
    "            tmps += c\n",
    "            # print(left, right, ans, tmps)\n",
    "            while(tmps >= s):\n",
    "                ans = min(ans, right - left)\n",
    "                d = nums[left]\n",
    "                left += 1\n",
    "                tmps -= d\n",
    "                # print(left, right, ans, tmps)\n",
    "        # if ans == 1<<31:\n",
    "        #     ans = 0\n",
    "        return 0 if ans == 1<<31 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        \n",
    "        if not nums or sum(nums) < s:\n",
    "            return 0\n",
    "\n",
    "        start, end = 0, 0\n",
    "\n",
    "        win_sum = 0\n",
    "\n",
    "        res = float('inf')\n",
    "\n",
    "        for end in range(len(nums)):\n",
    "            win_sum += nums[end]\n",
    "\n",
    "            while win_sum >= s:\n",
    "                res = min(res, end - start + 1)\n",
    "                win_sum -= nums[start]\n",
    "                start += 1        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        right, sum_num = 0, 0\n",
    "        length = len(nums)\n",
    "        ans = length + 1\n",
    "        for i, v in enumerate(nums):\n",
    "            while right < length and sum_num < s:\n",
    "                sum_num += nums[right]\n",
    "                right += 1\n",
    "            if sum_num >= s:\n",
    "                ans = min(ans, right - i)\n",
    "            sum_num -= v\n",
    "        if ans == length + 1:\n",
    "            return 0\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        window = []\n",
    "        start = 0\n",
    "        end = len(nums)-1\n",
    "        sum = 0\n",
    "        index = 0\n",
    "        end_flag = 0\n",
    "        while start <= end:\n",
    "            if sum >= s:                \n",
    "                window.insert(0, index-start+end_flag)\n",
    "                sum -= nums[start]\n",
    "                start += 1\n",
    "                if start > end:\n",
    "                    break\n",
    "            else:\n",
    "                if index > end:\n",
    "                    index = end\n",
    "                    end_flag = 1\n",
    "                    if sum < s:\n",
    "                        break\n",
    "                else:\n",
    "                    sum += nums[index]\n",
    "                    index += 1\n",
    "\n",
    "        if len(window) == 0:\n",
    "            return 0\n",
    "    \n",
    "        return min(window)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = right = 0\n",
    "        s = 0\n",
    "        res = n + 1\n",
    "        while right < n:\n",
    "            s += nums[right]\n",
    "            if s >= target:\n",
    "                while s - target >= nums[left]:\n",
    "                    s -= nums[left]\n",
    "                    left += 1\n",
    "                res = min(res, right - left + 1)\n",
    "                print(left, right)\n",
    "            right += 1\n",
    "        if res < n + 1:\n",
    "            return res \n",
    "        return 0\n",
    "                    \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        res = float(\"inf\")\n",
    "        Sum = 0\n",
    "        index = 0\n",
    "        for i in range(len(nums)):\n",
    "            Sum += nums[i]\n",
    "            while Sum >= target:\n",
    "                res = min(res, i - index + 1)\n",
    "                Sum -= nums[index]\n",
    "                index += 1\n",
    "        return 0 if res == float(\"inf\") else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        # 先来个暴力吧\n",
    "        if not nums:\n",
    "            return 0\n",
    "        res = len(nums)+1  # 这里要写加一 因为存在全是1  的和\n",
    "        for i in range(len(nums)):\n",
    "            total = 0\n",
    "            for j in range(i,len(nums)):\n",
    "                total += nums[j]\n",
    "                if total>=target:\n",
    "                    res = min(res,j-i+1)\n",
    "                    break \n",
    "        return 0 if res == len(nums)+1 else res    \n",
    "    '''if res == len(nums)+1:\n",
    "            return 0\n",
    "        else:\n",
    "            return res'''\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        left = 0\n",
    "        current = 0\n",
    "        result = float('inf')\n",
    "        for right in range(len(nums)):\n",
    "            current += nums[right]\n",
    "            while current >= target:\n",
    "                result = min(right - left + 1, result)\n",
    "                current -= nums[left]\n",
    "                left += 1\n",
    "        if result == float('inf'):\n",
    "            return 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        ret = list()\n",
    "\n",
    "        if not nums:\n",
    "            return (0)\n",
    "        if len(nums) == 1:\n",
    "            if nums[0] == target:\n",
    "                return(1)\n",
    "            else:\n",
    "                return(0)\n",
    "\n",
    "        left, right = 0, 1\n",
    "        while (left < right) and right <= len(nums):\n",
    "            if sum(nums[left: right]) >= target:\n",
    "                if not ret or right - left < len(ret):\n",
    "                    ret = nums[left: right]\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "\n",
    "        return len(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        sums = [0]\n",
    "        for i in range(n):\n",
    "            sums.append(sums[-1] + nums[i])\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            target = s + sums[i - 1]\n",
    "            bound = bisect.bisect_left(sums, target)\n",
    "            if bound != len(sums):\n",
    "                ans = min(ans, bound - (i - 1))\n",
    "        \n",
    "        return 0 if ans == n + 1 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = n + 1\n",
    "        sums = [0]\n",
    "        for i in range(n):\n",
    "            sums.append(sums[-1] + nums[i])\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            target = s + sums[i - 1]\n",
    "            bound = bisect.bisect_left(sums, target)\n",
    "            if bound != len(sums):\n",
    "                ans = min(ans, bound - (i - 1))\n",
    "        \n",
    "        return 0 if ans == n + 1 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        if sum(nums) < target:\n",
    "            return 0\n",
    "        elif sum(nums) == target:\n",
    "            return m\n",
    "        \n",
    "        dfs = [0] * len(nums)\n",
    "        dfs_list = [0] * len(nums)\n",
    "        result = None\n",
    "\n",
    "\n",
    "        previous = nums[0]\n",
    "        if previous >= target:\n",
    "            dfs[0] = 1\n",
    "            dfs_list[0] = 0\n",
    "        j = 1\n",
    "        while previous < target:\n",
    "            previous += nums[j]\n",
    "            if previous >= target:\n",
    "                dfs[0] = j + 1\n",
    "                dfs_list[0] = j\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "\n",
    "        for i in range(1, m):\n",
    "            game_over = False\n",
    "            previous -= nums[i-1]\n",
    "            if previous >= target:\n",
    "                dfs[i] = dfs[i-1] - 1\n",
    "                dfs_list[i] = dfs_list[i-1]\n",
    "                continue\n",
    "            j = dfs_list[i-1] + 1\n",
    "            while previous < target:      \n",
    "                if j >= len(nums):\n",
    "                    dfs[i:] = [float('inf')] * (m-i)\n",
    "                    game_over = True\n",
    "                    break\n",
    "                previous += nums[j]\n",
    "                if previous >= target:\n",
    "                    dfs[i] = j - i + 1\n",
    "                    dfs_list[i] = j\n",
    "                else:\n",
    "                    j += 1\n",
    "            \n",
    "            if game_over:\n",
    "                break\n",
    "\n",
    "        return(min(dfs))\n",
    "        # i = dfs.index(min(dfs))\n",
    "        # j = dfs_list[i] \n",
    "        # print(dfs, dfs_list)\n",
    "        # if i == j:\n",
    "        #     return nums[i]\n",
    "        # else:\n",
    "        #     return nums[i:j+1]\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "            \n",
    "                    \n",
    "                    \n",
    "                \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        idx=[0]*n\n",
    "        dp[0]=nums[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i]+dp[i-1]<target:\n",
    "                dp[i]=nums[i]+dp[i-1]\n",
    "                idx[i]=idx[i-1]\n",
    "            else:\n",
    "                temp=dp[i-1]+nums[i]\n",
    "                for j in range(idx[i-1],i+1):\n",
    "                    temp-=nums[j]\n",
    "                    if temp<target:\n",
    "                        break\n",
    "                idx[i]=j\n",
    "                if temp<target:\n",
    "                    dp[i]=temp+nums[j]\n",
    "                    \n",
    "        ans=float('inf')\n",
    "        for i in range(n):\n",
    "            if dp[i]>=target:\n",
    "                ans=min(i-idx[i]+1,ans)\n",
    "        if ans==float('inf'):\n",
    "            ans=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        # start = 0\n",
    "        # end = 0\n",
    "        # total = 0\n",
    "        # re = []\n",
    "        # while end < len(nums):\n",
    "        #     total = total + nums[end]\n",
    "        #     while total >= target:\n",
    "        #         re.append(end-start+1)\n",
    "        #         total = total - nums[start]\n",
    "        #         start += 1\n",
    "        #     end += 1\n",
    "        # if re == []:\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     return min(re)\n",
    "        s = [0]\n",
    "        re = []\n",
    "        for i in range(len(nums)):\n",
    "            s.append(s[-1]+nums[i])\n",
    "        for i in range(len(nums)):\n",
    "            l = i\n",
    "            r = len(s) - 1\n",
    "            while l <= r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if s[mid] - s[i] < target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if l <= len(s)-1 and s[l] - s[i] >= target:\n",
    "                re.append(l - i)\n",
    "        if re == []:\n",
    "            return 0\n",
    "        else:\n",
    "            return min(re)\n",
    "\n",
    "# class Solution:\n",
    "#     def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "#         if not nums:\n",
    "#             return 0\n",
    "        \n",
    "#         n = len(nums)\n",
    "#         ans = n + 1\n",
    "#         start, end = 0, 0\n",
    "#         total = 0\n",
    "#         while end < n:\n",
    "#             total += nums[end]\n",
    "#             while total >= s:\n",
    "#                 ans = min(ans, end - start + 1)\n",
    "#                 total -= nums[start]\n",
    "#                 start += 1\n",
    "#             end += 1\n",
    "        \n",
    "#         return 0 if ans == n + 1 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        import itertools\n",
    "        import bisect\n",
    "        acc = list(itertools.accumulate(nums))\n",
    "        n = len(nums)\n",
    "        dp = [float('inf')] * n \n",
    "        for i in range(len(nums)):\n",
    "            thresh = target - nums[i]\n",
    "            thresh2 = acc[i] - target\n",
    "            if thresh <= 0:\n",
    "                dp[i] = 1\n",
    "            elif i-1 >= 0:\n",
    "                idx = bisect.bisect(acc[:i], thresh2)\n",
    "                if idx == 0:\n",
    "                    if acc[i] >= target:\n",
    "                        dp[i] = i + 1\n",
    "                    else:\n",
    "                        dp[i] = float('inf')\n",
    "                else:\n",
    "                    dp[i] = i - idx + 1\n",
    "            elif i==0:\n",
    "                if nums[i] >= target:\n",
    "                    dp[i] = 1\n",
    "                else:\n",
    "                    dp[i] = float('inf')\n",
    "        print(dp)\n",
    "        for element in dp:\n",
    "            if element <= n+1:\n",
    "                return min(dp)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        left, right = 0, 0\n",
    "        res = []\n",
    "        num = nums[0]\n",
    "        while left < len(nums) and right < len(nums):\n",
    "            if num < target:\n",
    "                right += 1\n",
    "                if right < len(nums):\n",
    "                    num += nums[right]\n",
    "            else:\n",
    "                res.append([left, right])\n",
    "                num -= nums[left]\n",
    "                left += 1\n",
    "        ans = float('inf')\n",
    "        for one in res:\n",
    "            ans = min(ans, one[1]-one[0])\n",
    "        return ans+1 if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        left, right = 0, 0\n",
    "        res = []\n",
    "        num = nums[0]\n",
    "        while left < len(nums) and right < len(nums):\n",
    "            if num < target:\n",
    "                right += 1\n",
    "                if right < len(nums):\n",
    "                    num += nums[right]\n",
    "            else:\n",
    "                res.append([left, right])\n",
    "                num -= nums[left]\n",
    "                left += 1\n",
    "        ans = float('inf')\n",
    "        for one in res:\n",
    "            ans = min(ans, one[1]-one[0])\n",
    "        return ans+1 if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        presum = {}\n",
    "        presum[-1] = 0\n",
    "        sum_ = 0\n",
    "        res = float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] >= target:\n",
    "                return 1\n",
    "            sum_ += nums[i]\n",
    "            presum[i] = sum_\n",
    "\n",
    "            # 二分\n",
    "            l, r = -1, i - 1\n",
    "            cur = -2\n",
    "            while l <= r:\n",
    "                m = l + (r - l) // 2\n",
    "                if sum_ - presum[m] > target:\n",
    "                    cur = m\n",
    "                    l = m + 1\n",
    "                elif sum_ - presum[m] < target:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    cur = m\n",
    "                    break\n",
    "            # print(i, cur, presum)\n",
    "            if cur >= -1:\n",
    "                res = min(res, i - cur)\n",
    "        return res if res != float('inf') else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        size, cnt = len(nums), len(nums)\n",
    "        d = deque()\n",
    "        result = size\n",
    "        f = 0\n",
    "        if size == 1:\n",
    "            if nums[0] >= target:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        elif sum(nums) == target:\n",
    "            return size\n",
    "        else:\n",
    "            temp = 0\n",
    "            sumd = 0\n",
    "            while size > 0: \n",
    "                x = nums.pop()\n",
    "                d.append(x)\n",
    "                sumd += x\n",
    "                if sumd >= target:\n",
    "                    temp += 1\n",
    "                    result = min(result, temp)\n",
    "                    while sumd >= target:\n",
    "                        y = d.popleft()\n",
    "                        sumd -= y\n",
    "                        temp -= 1\n",
    "                    result = min(result, temp + 1)\n",
    "                    f = 1\n",
    "                else:\n",
    "                    temp += 1\n",
    "                size -= 1\n",
    "            return 0 if result == cnt and f == 0 else result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        candidate = []\n",
    "        while i < len(nums):\n",
    "            if i == j:\n",
    "                if nums[i] >= s:\n",
    "                    return 1\n",
    "                i += 1\n",
    "            value = sum(nums[j: i + 1])\n",
    "            if value >= s:\n",
    "                length = i - j + 1\n",
    "                candidate.append([i, j, length, value])\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        if not candidate:\n",
    "            return 0\n",
    "        min_value = candidate[0][2]\n",
    "        min_idx = 0\n",
    "        for idx, can in enumerate(candidate, 0):\n",
    "            if can[2] < min_value:\n",
    "                min_value = can[2]\n",
    "                min_idx = idx\n",
    "        result = candidate[min_idx]\n",
    "        return result[2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, s, nums) -> int:\n",
    "        if sum(nums) < s:\n",
    "            return 0\n",
    "        if sum(nums) == s:\n",
    "            return len(nums)\n",
    "        if s in nums:\n",
    "            return 1\n",
    "        l, r, win = 0, 0, nums[0]\n",
    "        res, through_path = set(), set()\n",
    "        while l <= r and r < len(nums):\n",
    "            if (l, r) in through_path:\n",
    "                return min(res) if res else 0\n",
    "            else:\n",
    "                through_path.add((l, r))\n",
    "            if win >= s:\n",
    "                res.add(r-l+1)\n",
    "                win -= nums[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                if r+1 < len(nums):\n",
    "                    r += 1\n",
    "                    win += nums[r]\n",
    "                else:\n",
    "                    l -= 1\n",
    "                    win += nums[l]\n",
    "        return min(res) if res else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        i = j=0\n",
    "        min = len(nums)\n",
    "        sum = 0\n",
    "        result=[]\n",
    "        for j in range(len(nums)+1):\n",
    "            if (sum < target):\n",
    "                if(j>=len(nums)):\n",
    "                    break\n",
    "                result.append(nums[j])\n",
    "                sum = sum + nums[j]\n",
    "            elif (sum >= target):\n",
    "                while(sum - nums[i] >= target):\n",
    "                    sum = sum - nums[i]\n",
    "                    del(result[0])\n",
    "                    i = i + 1\n",
    "                l = j-i\n",
    "                if (l < min):\n",
    "                    min = l\n",
    "                if (j >= len(nums)):\n",
    "                    break\n",
    "                sum = sum + nums[j]\n",
    "                result.append(nums[j])\n",
    "        if(sum<target):\n",
    "            return 0\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        res = 10000000\n",
    "        sums = 0\n",
    "        j = 0\n",
    "        for i in range(len(nums)):\n",
    "            sums +=nums[i]\n",
    "            while(sums>=target):\n",
    "                res = min(res,i-j+1)\n",
    "                sums-=nums[j]\n",
    "                j+=1\n",
    "        return 0 if res == 10000000 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        left = 0\n",
    "        Sum = 0\n",
    "        min_len = l + 1\n",
    "        for right in range(l):\n",
    "            Sum += nums[right]\n",
    "            while Sum >= target:\n",
    "                min_len = min(right - left + 1, min_len)\n",
    "                Sum -= nums[left]\n",
    "                left += 1\n",
    "        if min_len <= l:\n",
    "            return min_len\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        len_min = 9999999999\n",
    "        now = []\n",
    "        first_index = 0\n",
    "        sum_l = 0\n",
    "        # print(sum(nums))\n",
    "        # len_count = 1\n",
    "        while nums:\n",
    "            add = nums.pop()\n",
    "            sum_l += add\n",
    "            now.append(add)\n",
    "            if sum_l >= target:\n",
    "                sum_tmp = sum_l\n",
    "                len_n = len(now)\n",
    "                for i in range(len_n):\n",
    "                    sum_tmp -= now[i]\n",
    "                    if sum_tmp < target:\n",
    "                        break\n",
    "                    sum_l = sum_tmp\n",
    "                # print(now)\n",
    "                count = len_n - i\n",
    "                len_min = len_min if len_min < count else count\n",
    "                now = now[-count:]\n",
    "                \n",
    "\n",
    "        # while nums:\n",
    "        #     now.append(nums.pop())\n",
    "        #     if sum(now) >= target:\n",
    "        #         n = 0\n",
    "        #         count = 0\n",
    "        #         for i in now[::-1]:\n",
    "        #             count += 1\n",
    "        #             n += i\n",
    "        #             if n >= target:\n",
    "        #                 len_min = len_min if len_min < count else count\n",
    "        #                 break\n",
    "        #         now = now[-count:]\n",
    "        return len_min if len_min!=9999999999 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        # 1.其实从一开始我就想到了滑动窗口，没仔细想以为2层循环会导致n^2的复杂度\n",
    "        # 其实最大都是移动到头 是2n = O(n)\n",
    "\n",
    "        # 另外二分查找我也想的接近了，还差一点，没想清楚其实索引作为标的\n",
    "\n",
    "        # 方法一，移动窗口\n",
    "        # star, end = 0, 0\n",
    "        # sum_num = 0\n",
    "        # n = len(nums)\n",
    "        # min_len = n+1\n",
    "        # for i in range(n):\n",
    "        #     sum_num += nums[i]\n",
    "        #     while sum_num >=target:\n",
    "        #         min_len = min(min_len, i-star+1)\n",
    "        #         sum_num -= nums[star]\n",
    "        #         star += 1\n",
    "        # if min_len == n+1:return 0\n",
    "        # return min_len\n",
    "\n",
    "        # 方法二， 前缀和 在在里边进行二分查找\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        pre_sum = []\n",
    "        for i in range(n):\n",
    "            if not pre_sum:pre_sum.append(nums[i])\n",
    "            else:pre_sum.append(nums[i] + pre_sum[i-1])  # 前缀和\n",
    "        \n",
    "        pre_sum = [0] + pre_sum\n",
    "        # print(pre_sum)\n",
    "\n",
    "        def find_index(pre_sum, ob): # 和之前一个有重复数据找位置的题目一样\n",
    "            # 找>= ob的最左边位置\n",
    "            left, right = 0, len(pre_sum)-1\n",
    "            while left<=right:\n",
    "                mid = (left+ right)//2\n",
    "                if mid == right:\n",
    "                    if pre_sum[left] >= ob:\n",
    "                        return left\n",
    "                    return -1\n",
    "                if pre_sum[mid] >= ob:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return -1\n",
    "        \n",
    "        min_len = n+1\n",
    "        for s in range(n+1): # 起点,以每个下表开始，找最短长度\n",
    "            ob = target+pre_sum[s] # 找大于等于ob的最左边的一个\n",
    "            index = find_index(pre_sum, ob)\n",
    "            if index != -1:\n",
    "                # print('s', s, 'index:', index, index-s)\n",
    "                min_len = min(min_len, index-s)\n",
    "        \n",
    "        if min_len == n+1:return 0\n",
    "        return min_len\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        result = float('inf')   # 定义一个无限大的数\n",
    "        Sum = 0     # 滑动窗口数值之和\n",
    "        i = 0       # 滑动窗口起始位置\n",
    "        for j in range(len(nums)):\n",
    "            Sum += nums[j]\n",
    "            while Sum >= target:\n",
    "                result = min (result, j-i+1)\n",
    "                Sum -= nums[i]\n",
    "                i = i + 1\n",
    "        if result == float('inf'):\n",
    "            return 0\n",
    "        else:\n",
    "            return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        result = float('inf')   # 定义一个无限大的数\n",
    "        Sum = 0     # 滑动窗口数值之和\n",
    "        i = 0       # 滑动窗口起始位置\n",
    "        for j in range(len(nums)):\n",
    "            Sum += nums[j]\n",
    "            while Sum >= target:\n",
    "                result = min (result, j-i+1)\n",
    "                Sum -= nums[i]\n",
    "                i = i + 1\n",
    "        if result == float('inf'):\n",
    "            return 0\n",
    "        else:\n",
    "            return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        #preSum\n",
    "        n=len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(len(nums)):\n",
    "            pre[i+1]=pre[i]+nums[i]\n",
    "        #binarysearch\n",
    "        ans = float('inf')\n",
    "        l,r = 0,0\n",
    "        while r<n+1:\n",
    "      \n",
    "            if pre[r]-pre[l] <target:\n",
    "                r+=1\n",
    "            while r<n+1 and pre[r]-pre[l] >=target:\n",
    "                ans = min(ans,r-l)\n",
    "                l+=1\n",
    "        return 0 if ans ==  float('inf') else ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        start = 0\n",
    "        end = 0\n",
    "        sum = 0\n",
    "        result = float('inf')\n",
    "        while end < len(nums):\n",
    "            sum += nums[end]\n",
    "            while sum >= target:\n",
    "                result = min(result , end-start + 1)\n",
    "                sum -= nums[start]\n",
    "                start += 1\n",
    "            end += 1\n",
    "        return result if result != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        ans = length + 1\n",
    "\n",
    "        l, r = 0, 0\n",
    "        sum = nums[0]\n",
    "        \n",
    "        while l <= r and r <= length - 1:\n",
    "            if r == length-1 and sum < target:\n",
    "                break\n",
    "\n",
    "            while sum < target and r + 1 <= length - 1:\n",
    "                r += 1\n",
    "                sum += nums[r]\n",
    "\n",
    "            if sum >= target:\n",
    "                ans = min(r - l + 1, ans)\n",
    "\n",
    "            while sum >= target:\n",
    "                l += 1\n",
    "                sum -= nums[l-1]\n",
    "            \n",
    "            if sum + nums[l-1] >= target:\n",
    "                ans = min(r - l + 2, ans)\n",
    "\n",
    "        return ans if ans != length + 1 else 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        left = 0\n",
    "        t = 0\n",
    "        res = inf\n",
    "        for right in range(len(nums)):\n",
    "            t += nums[right]\n",
    "            while left < right and t - nums[left] >= target:\n",
    "                t -= nums[left]\n",
    "                left += 1\n",
    "            \n",
    "            if t >= target:\n",
    "                \n",
    "                res = min(res, right - left + 1)\n",
    "        return 0 if res == inf else res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
